package 动态规划.股票买卖问题;

import static java.lang.Math.max;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-20
 */
public class 最大获利 {
    public static void main(String[] args) {
        System.out.println(maxProfit_k_any(new int[]{3, 1, 5, 2, 6, 3}, 3));
        System.out.println(maxProfit_k_inf(new int[]{3, 1, 5, 2, 6, 3}));
        System.out.println(maxProfit_k_1(new int[]{3, 1, 8, 2, 6, 3}));
    }



/*
    dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
    max( 选择 rest , 选择 sell )
    解释：今天我没有持有股票，有两种可能：
    要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
    要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。
    dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
    max( 选择 rest , 选择 buy )
    解释：今天我持有着股票，有两种可能： 要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
    要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。
    */

    /*
    dp[-1][k][0] = 0
    解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。
    dp[-1][k][1] = -infinity
    解释：还没开始的时候，是不可能持有股票的，⽤负⽆穷表⽰这种不可能。
    dp[i][0][0] = 0
    解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。
    dp[i][0][1] = -infinity
    解释：不允许交易的情况下，是不可能持有股票的，⽤负⽆穷表⽰这种不可能。
    */

    static int i = 1;
    static int k = 1;
    //买卖次数
    public static int[] prices = new int[i + 1];
    public static int[][][] dp = new int[i + 1][k + 1][2];

    static {

        //        把上⾯的状态转移⽅程总结⼀下：
        //        base case：
        dp[0][k][0] = dp[i][0][0] = 0;
        dp[0][k][1] = dp[i][0][1] = Integer.MIN_VALUE;
        //      状态转移⽅程：
        dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
        dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
    }

    /**
     * 第⼀题，k = 1         *
     */
    public static int maxProfit_k_1(int[] prices) {
        int[] dp = new int[prices.length];
        int buyPrice = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.max(dp[i - 1], buyPrice + prices[i]);
            buyPrice = Math.max(buyPrice, -prices[i]);
        }
        return dp[prices.length - 1];
    }
    /**
     * 第二题，k = n         *
     */
    static int maxProfit_k_inf(int[] prices) {
        int[][] status = new int[prices.length][2];
        for (int i = 0; i < prices.length; i++) {
            if (i == 0) {
                status[0][1] = -prices[i];
                status[i][0] = 0;
                continue;
            }
            status[i][0] = Math.max(status[i - 1][0], prices[i] + status[i - 1][1]);
            status[i][1] = Math.max(status[i - 1][1], -prices[i] + status[i - 1][0]);
        }
        return status[prices.length - 1][0];
    }

    /**
     * 交易无限次，O(n)
     *
     * @param prices
     * @return
     */

    /**
     * 交易无限次，O(1)
     *
     * @param prices
     * @return
     */
    static int maxProfit_k_inf_sim(int[] prices) {
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
        }
        return dp_i_0;
    }

    /**
     * 交易有冷静期为1天
     * dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
     * 解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，⽽不是 i-1
     */
    static int maxProfit_with_cool(int[] prices) {
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        int dp_pre_0 = 0; // 代表 dp[i-2][0]
        for (int i = 0; i < n; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
            dp_pre_0 = temp;
        }
        return dp_i_0;
    }

    /**
     * 交易有费用
     * dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
     * dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i] - fee)
     * 解释：相当于买⼊股票的价格升⾼了。在第⼀个式⼦⾥减也是⼀样的，相当于卖出股票的价格减⼩
     *
     * @param prices
     * @param fee
     * @return
     */
    static int maxProfit_with_fee(int[] prices, int fee) {
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
        }
        return dp_i_0;
    }

    /**
     * 交易次数为2
     *
     * @param prices
     * @return
     */
    static int maxProfit_k_2(int[] prices) {
        int dp_i10 = 0, dp_i11 = Integer.MIN_VALUE;
        int dp_i20 = 0, dp_i21 = Integer.MIN_VALUE;
        for (int price : prices) {
            dp_i20 = Math.max(dp_i20, dp_i21 + price);
            dp_i21 = Math.max(dp_i21, dp_i10 - price);
            dp_i10 = Math.max(dp_i10, dp_i11 + price);
            dp_i11 = Math.max(dp_i11, -price);
        }
        return dp_i20;
    }

    /**
     * 交易次数为k
     *
     * @param prices
     * @return
     */
    static int maxProfit_k_any(int[] prices, int max_k) {

        int n = prices.length;
        if (max_k > n / 2) return maxProfit_k_inf(prices);
        int[][][] dp = new int[n][max_k + 1][2];
        for (int i = 0; i < n; i++)
            for (int k = max_k; k >= 1; k--) {
                if (i - 1 == -1) {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        return dp[n - 1][max_k][0];
    }

}